class Solution {
public: 
    vector<vector<int> > edges;
    vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) {
        edges.resize(n);
        for(auto& vc : paths){
            edges[vc[0]-1].push_back(vc[1]-1);
            edges[vc[1]-1].push_back(vc[0]-1);
        }
        
        vector<int> ret(n);
        for(int i = 0;i < n;i++){
            int color[5] = {0};
            for(int& j : edges[i]){
                color[ret[j]] = 1;
            }
            
            for(int k = 1;k <= 4;k++){
                if(color[k] == 0){
                    ret[i] = k;
                    break;
                }
            }
        }
        return ret;
    }
};
